package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;

//分支限界求解最大背包问题
public class Pra3 {
    public int maxValue(int[] v, int[] m, int V) {
        //将每个背包按照单位体积排序
        int[][] p = new int[v.length][2];
        Queue<int[]> queue = new PriorityQueue<>((p1, p2) -> {
            double r1 = p1[0] / (double)p1[1];
            double r2 = p2[0] / (double)p2[1];
            if (r1 > r2) return -1;
            else if (r1 < r2) return 1;
            else return 0; 
        });

        for (int i = 0; i < v.length; i++) {
            queue.offer(new int[]{v[i], m[i]});
        }
        int idx = 0;
        while (!queue.isEmpty()) {
            p[idx++] = queue.poll();
        }
        System.out.println(Arrays.deepToString(p));
        dfs(p, 0, V, 0);
        return res;
    }
    int res = 0; //界
    public void dfs(int[][] p, int idx, int cur, int sum) {
        if (idx == p.length) {
            res = Math.max(sum, res);
            return;
        }
        //计算当前的估价上界
        double price = cur * p[idx][0] / (double)p[idx][1] + sum;
        if (price > res) {
            //只有价值上界大于当前的界，才有搜索的必要
            if (cur >= p[idx][1])
                dfs(p, idx + 1, cur - p[idx][1], sum+p[idx][0]); //拿下当前物品
            dfs(p, idx + 1, cur, sum);
        }
    }

    @Test
    public void test() {
        
        int[] V = new int[]{3,4,5,8,10};
        int[] M = new int[]{2,3,4,5,9};
        int res1 = maxValue(V, M, 20);

        int res = maxValue2(V, M, 20);
        System.out.println(res == res1);
    }

    //动态规划
    public int maxValue2(int[] v, int[] m, int V) {
        int len = v.length;
        int[][] f = new int[len + 1][V + 1];
        f[len][V] = 0;
        // f[len][]
        for (int i = len - 1; i >= 0; i--) {
            for (int j = V; j >= 0; j--) {
                /*    //多重背包
                for (int k = 0; k * m[i] <= j; k++) {
                    f[i][j] = Math.max(f[i][j], f[i + 1][j - k * m[i]] + v[i]);
                } */
                //0-1背包 
                f[i][j] = f[i + 1][j];
                if (j >= m[i]) {
                    f[i][j] = Math.max(f[i][j], f[i + 1][j - m[i]] + v[i]);
                }
            }
        }
        System.out.println(Arrays.deepToString(f));
        return f[0][V];
    }
}
